package sorted;

import java.util.Arrays;

public class S06_QuickSort {

    public static void main(String[] args) {
        int[] arr = {5,7,2,3,4,1,6,18,9,10,16,56,34,23,11,12,31,17,15};
        quickSort(arr, 0, arr.length-1);

        System.out.println("排序后的数组为："+ Arrays.toString(arr));
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low < high){
            int mid = quick(array, low, high);
            if (mid>0) quickSort(array, low, mid-1);
            if (mid<array.length-2) quickSort(array, mid+1, high);
        }
    }

    public static int quick(int[] array, int low, int high){
        int pivot = array[high];
        int point= low;

        for (int i = low; i < high; i++) {
            if (array[i] < pivot){
                int temp = array[point];
                array[point] = array[i];
                array[i] = temp;
                point++;
            }
        }

        int temp = array[point];
        array[point] = array[high];
        array[high] = temp;

        return point;

    }
}

